#include <stdio.h>
#include <assert.h>
#include<unistd.h>
#include "avl_tree.h"

inline avl_node_t *avl_parent(avl_node_t *node)
{
	return node->parent;
}       

inline void avl_set_parent(avl_node_t *node, avl_node_t *p)
{
	node->parent = p;
}

inline void avl_link_node(avl_node_t * node, avl_node_t * parent,
		avl_node_t ** avl_link)
{
	node->parent = parent;
	node->avl_left = node->avl_right = NULL;
	*avl_link = node;
}

avl_node_t *avl_first(avl_root_t *root)
{
	avl_node_t *n;

	n = root->node;
	if (!n)
		return NULL;
	while (n->avl_left)
		n = n->avl_left;
	return n;
}

avl_node_t *avl_next(avl_node_t *node)
{
	avl_node_t *p;

	if (node->avl_right) {
		node = node->avl_right;
		while(node->avl_left)
			node = node->avl_left;
		return node;
	}
	while((p = avl_parent(node)) && node == p->avl_right)
		node = p;
	return p;
}

inline int avl_bf(avl_node_t *node)
{
	return node->right_len - node->left_len;
}


void __avl_rotate_left(avl_node_t *node, avl_root_t *root)
{
	avl_node_t *r = node->avl_right;
	avl_node_t *p = avl_parent(node);

	/* move right's left to node's right */
	if ((node->avl_right = r->avl_left))
		avl_set_parent(r->avl_left, node);
	
	/* move node to right's left */
	r->avl_left = node;
	avl_set_parent(node, r);
	
	/* move right to parent's sun */
	if (p) {
		if (node == p->avl_left)
			p->avl_left = r;
		else 
			p->avl_right = r;
	} else 
		root->node = r;
	avl_set_parent(r, p);
}

void __avl_rotate_right(avl_node_t *node, avl_root_t *root)
{
	avl_node_t *l = node->avl_left;
	avl_node_t *p = avl_parent(node);
	
	/* move left's right to node's left */
	if ((node->avl_left = l->avl_right))
		avl_set_parent(l->avl_right, node);

	/* move node to left's right */
	l->avl_right = node;
	avl_set_parent(node, l);

	/* move left to parent's sun */
	if (p) {
		if (node == p->avl_left)
			p->avl_left = l;
		else 
			p->avl_right = l;
	} else 
		root->node = l;
	avl_set_parent(l, p);
}

void avl_insert_adjust(avl_node_t *node, avl_root_t *root)
{
	avl_node_t *p, *gp;

	p = avl_parent(node);
	if (!p)
		return;

	gp = avl_parent(p);
	if (!gp)
		return;
	
	if (avl_bf(gp) > -2 && avl_bf(gp) < 2)
		return;


	if (avl_bf(gp) == -2) {
		if (avl_bf(p) == -1) {
			__avl_rotate_right(gp, root);
		} else if (avl_bf(p) == 1) {
			__avl_rotate_left(p, root);
			__avl_rotate_right(gp, root);
		}
		else 
			printf("p->bf error\n");
	} else if (avl_bf(gp)== 2) {
		if (avl_bf(p) == -1) {
			__avl_rotate_left(gp, root);
		} else if (avl_bf(p) == 1) {
			__avl_rotate_right(p, root);
			__avl_rotate_left(gp, root);
		}
		else 
			printf("p->bf error\n");
	} else 
		printf("gb->bf error\n");
}

#if 0
static void __avl_erase_color(avl_node_t *node, 
		avl_node_t *parent, avl_root_t *root)
{
	avl_node_t *other = NULL;

	while ((!node || avl_is_black(node)) && node != root->node) {
		if (node == parent->avl_left) {
			other = parent->avl_right;

			//if (other && avl_is_red(other)) {
			if (other && avl_is_red(other)) {
				avl_set_red(parent);
				avl_set_black(other);
				__avl_rotate_left(parent, root);
				other = parent->avl_right;
			}
			//if (other && (other->avl_left && avl_is_black(other->avl_left))
			if ((!other->avl_left || avl_is_black(other->avl_left))
				&& (!other->avl_right || avl_is_black(other->avl_right))) {
				/* we don't need to judge if the parent is black */
				/*
				avl_set_red(other);
				if (avl_is_black(parent)) {
					node = parent;
					parent = avl_parent(parent);
					continue;
				}
				avl_set_black(parent);
				break;
				*/
				avl_set_red(other);
				node = parent;
				parent = avl_parent(parent);
			} else {
				//if (other && (other->avl_left && avl_is_red(other->avl_left))) {
				if (other->avl_left && avl_is_red(other->avl_left)) {
					avl_set_black(other->avl_left);
					avl_set_red(other);
					__avl_rotate_right(other, root);
					other = parent->avl_right;
				}
				avl_set_color(other, avl_color(parent));
				avl_set_black(parent);
				if (other->avl_right)
					avl_set_black(other->avl_right);
				__avl_rotate_left(parent, root);
				node = root->node;
				break;
			}
		} else {
			other = parent->avl_left;

			if (avl_is_red(other)) {
				avl_set_black(other);
				avl_set_red(parent);
				__avl_rotate_right(parent, root);
				other = parent->avl_left;
			}
			if ((!other->avl_left || avl_is_black(other->avl_left)) &&
				(!other->avl_right || avl_is_black(other->avl_right))) {
				avl_set_red(other);
				node = parent;
				parent = avl_parent(parent);
				
			} else {
				if (!other->avl_left || avl_is_black(other->avl_left)) {
					avl_set_black(other);
					if (other->avl_right)
						avl_set_black(other->avl_right);
					__avl_rotate_left(other, root);
					other = other->avl_right;
				}
				avl_set_color(other, avl_color(parent));
				avl_set_black(parent);
				if (other->avl_left)
					avl_set_black(other->avl_left);
				__avl_rotate_right(parent, root);
				node = root->node;
				break;
			}
		}
	}
	if (node)
		avl_set_black(node);
}

void avl_erase(avl_node_t *node, avl_root_t *root)
{
	avl_node_t *child, *parent;
	int color;

	if (!node->avl_left)
		child = node->avl_right;
	else if (!node->avl_right)
		child = node->avl_left;
	else {
		avl_node_t *next = NULL, *old = node;
		int tmp;

		next = node->avl_right;
		while (next->avl_left)
			next = next->avl_left;
		tmp = old->data;
		old->data = next->data;
		next->data = tmp;

		node = next;
	}

	parent = avl_parent(node);
	if(child)
		avl_set_parent(child, parent);
	if (parent) {
		if (node == parent->avl_left)
			parent->avl_left = child;
		else
			parent->avl_right = child;
	} else 
		root->node = child;

	color = avl_color(node);
	if (RB_BLACK == color)
		__avl_erase_color(child, parent, root);
}
#endif

